package 力扣;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yyq
 * @create 2022-05-03 15:43
 */
public class leetcode93 {
    public static void main(String[] args) {
        leetcode93 leetcode93=new leetcode93();
        List<String> list = leetcode93.restoreIpAddresses("101023");
        System.out.println(list);
    }
    public List<String> restoreIpAddresses(String s) {
        List<String> lists = new ArrayList<>();
        if(s.length()<4||s.length()>12){
            return lists;
        }
        int templength = 0;
        int startIndex = 0;
        int deep = 1;
        List<String> list=new ArrayList<>();
        backTracking(startIndex,s,templength,deep,list,lists);
        return lists;
    }


    private void backTracking(int startIndex, String s, int templength,int deep, List<String> list, List<String> lists) {
        // 如果深度为 4
        if (list.size()==4){
            if(templength==s.length()){
                lists.add(list.get(0)+"."+list.get(1)+"."+list.get(2)+"."+list.get(3));
            }
            return;
        }
        // 每一次 横向遍历的范围 不能超过startIndex 3，超过肯定不符合了。
        // 每次获取 startIndex 到 i 范围的数
        for (int i=startIndex;i<startIndex+3&&i<s.length();i++){
            // 如果 目前剩余的未装配的数长度 大于  deep * 3 剪支不行 小于 deep也不行
            if(s.length() - (i+1)>3*(4-deep) || (4-deep)>s.length() - (i+1)) continue;
            // 如果这个数大于 255 肯定不符合IP地址规则
            if(new Integer(s.substring(startIndex,i+1))>255) return;
            String substring = s.substring(startIndex, i + 1);
            if(substring.length()>1){
                // 不能包含前置0
                if(substring.charAt(0)=='0') return;
            }

            list.add(substring);
            templength = templength + (i + 1 - startIndex);
            deep++;
            backTracking(i+1,s,templength,deep,list,lists);
            deep--;
            templength = templength - (i + 1 - startIndex);
            list.remove(list.size()-1);
        }

    }
}
